package com.yuan.algorithms.competition;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年3月19日 下午4:38:50
 * @descript 求第十万零一个素数
 */
public class 筛法求第100001个素数 {

	static final int SIZE = 100000000;
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		int n = 100001;
		//筛选素数
		boolean[] nums = new boolean[SIZE];
		for (int i = 2; i < Math.sqrt(SIZE); i++) {
			if (nums[i]) {
				continue;
			}
			for (int j = 2; j <= SIZE / i; j++) {
				if (j*i < SIZE) {
					nums[j*i] = true;
				}
			}
		}
		int sum = 0;
		for (int i = 2; i < SIZE; i++) {
			if (!nums[i]) {
				++sum;
				if (sum==n) {
					System.out.println(i);
//					break;
				}
			}
		}
		System.out.println("Sum:"+sum);
		System.out.println();
		long end = System.currentTimeMillis();
		System.out.println("Time:" + (end - start));
	}

}
